//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
//
// 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 
//
// 示例 2： 
//
// 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// 
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
// Related Topics 链表 双指针 分治 排序 归并排序 👍 1496 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _148_SortList {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new _148_SortList().new Solution();
        ListNode head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
        System.out.print("原始：");
        showList(head);
        System.out.print("排序：");
        showList(solution.sortList(head));
//        showList(head);

        System.out.println("复习归并排序：");
        int[] nums = new int[]{3, 38, 5, 19, 20, 29, 33, 17, 12, 9, 35, 0, 37, 8, 23, 7, 22, 27};
        System.out.print("排序前：");
        System.out.println(Arrays.toString(nums));
        guiBing(nums);
        System.out.print("排序后：");
        System.out.println(Arrays.toString(nums));
    }

    private static void guiBing(int[] nums) {
        if (nums.length == 0 || nums.length == 1) return;

        process(nums, 0, nums.length - 1);
    }

    private static void process(int[] nums, int l, int r) {
        if (l == r) return;

        int mid = l + ((r - l) >> 1);
        process(nums, l, mid);
        process(nums, mid + 1, r);
        merge(nums, l, mid, r);
    }

    private static void merge(int[] nums, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int li = l;
        int ri = mid + 1;
        int i = 0;
        while (li <= mid && ri <= r) {
            help[i++] = nums[li] <= nums[ri] ? nums[li++] : nums[ri++];
        }
        while (li <= mid) {
            help[i++] = nums[li++];
        }
        while (ri <= r) {
            help[i++] = nums[ri++];
        }
        for (int j = 0; j < help.length; j++) {
            nums[l + j] = help[j];
        }
        return;
    }

    private static void showList(ListNode head) {
        if (head == null) {
            System.out.println("empty");
            return;
        }
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public ListNode sortList(ListNode head) {
            return sortList(head, null);
        }

        public ListNode sortList(ListNode head, ListNode tail) {
            if (head == null) {
                return head;
            }
            if (head.next == tail) {
                head.next = null;
                return head;
            }
            ListNode slow = head, fast = head;
            while (fast != tail) {
                slow = slow.next;
                fast = fast.next;
                if (fast != tail) {
                    fast = fast.next;
                }
            }
            ListNode mid = slow;
            ListNode list1 = sortList(head, mid);
            ListNode list2 = sortList(mid, tail);
            ListNode sorted = merge(list1, list2);
            return sorted;
        }

        public ListNode merge(ListNode head1, ListNode head2) {
            ListNode dummyHead = new ListNode(0);
            ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
            while (temp1 != null && temp2 != null) {
                if (temp1.val <= temp2.val) {
                    temp.next = temp1;
                    temp1 = temp1.next;
                } else {
                    temp.next = temp2;
                    temp2 = temp2.next;
                }
                temp = temp.next;
            }
            if (temp1 != null) {
                temp.next = temp1;
            } else if (temp2 != null) {
                temp.next = temp2;
            }
            return dummyHead.next;
        }
    }


    // 用一下归并排序,有问题
    class Solution2 {
        public ListNode sortList(ListNode head) {
            return sortList(head, null);//不包括后者
        }

        private ListNode sortList(ListNode head, ListNode tail) {
            if (head == null || head.next == tail) return head;

            ListNode fast = head;
            ListNode slow = head;
            while (fast != tail) {
                slow = slow.next;
                fast = fast.next;
                if(fast != tail) fast = fast.next;
            }
            ListNode list1 = sortList(head, slow);
            ListNode list2 = sortList(slow, tail);
            return merge(list1, list2, tail);
        }

        private ListNode merge(ListNode head1, ListNode head2, ListNode tail) {
            ListNode dummyHead = new ListNode(0);
            ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
            while (temp1 != head2 && temp2 != tail) {
                if (temp1.val <= temp2.val) {
                    temp.next = temp1;
                    temp1 = temp1.next;
                } else {
                    temp.next = temp2;
                    temp2 = temp2.next;
                }
                temp = temp.next;
            }
            while (temp1 != head2) {
                temp.next = temp1;
                temp1 = temp1.next;
                temp = temp.next;
            }
            while (temp2 != tail) {
                temp.next = temp2;
                temp2 = temp2.next;
                temp = temp.next;
            }
            return dummyHead.next;
        }
    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    // 这个转成数组排序了
    class Solution1 {
        public ListNode sortList(ListNode head) {
            ListNode cur = head;
            int count = 0;
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            int[] nums = new int[count];
            int i = 0;
            cur = head;
            while (cur != null) {
                nums[i++] = cur.val;
                cur = cur.next;
            }
            Arrays.sort(nums);
            i = 0;
            cur = head;
            while (cur != null) {
                cur.val = nums[i++];
                cur = cur.next;
            }
            return head;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}